// todo: levelbound not accuracy
// todo: lowbound not accuracy
// todo:    cpofsubgraph not accuracy
// todo: unfold issue
// todo: utilize asapuc as asap

//#include "stdafx.h"
#include "stdafx.h"

// TODO: reference additional headers your program requires here
#include "Graph.h"
#include "HLS.h"
#include "FuncTimer.h"
#include <map>
#include <set>
#include <iostream>
#include <fstream>
#include <time.h>
#include <string>
#include <stdlib.h>
#include <stdio.h>
#include "Graph.h"
#include "FuncTimer.h"
#include "Config.h"
#include <vector>
#include <algorithm>
#include <list>
#include <limits.h>
//#include <boost/thread.hpp>
//#include <boost/thread/thread.hpp
//#include <windows.h>
//#include <direct.h>

//#include "stdafx.h"
using namespace std;


#if defined(_WIN32)

#elif defined(__unix__) || defined(__unix) || defined(unix) || (defined(__APPLE__) && defined(__MACH__))
using namespace __gnu_cxx;
#else
#error "unknown platform"
#endif
//#define INT_MAX 0x7fffffff
// optimization:
// ASAP
// ALAP
// pruning
static bool
	operator < ( Operation const &op1, Operation const &op2 )
{
	return ( (op1.sort_id > op2.sort_id) );//|| (op1.sort_id == op2.sort_id && op1.ASAP < op2.ASAP) );
}
int optimalScheduleTime = INT_MAX;
int listSchedulingTime = 0;
listorder global_listorder;
int badScheduleTime = 0;
int basicSchedulingTime = INT_MAX;
int w = INT_MAX;
int level_count = 0;

double dGetTickCount( )
{
#if defined(_WIN32)
	/* Windows -------------------------------------------------- */
	FILETIME createTime;
	FILETIME exitTime;
	FILETIME kernelTime;
	FILETIME userTime;
	if ( GetProcessTimes( GetCurrentProcess( ),
		&createTime, &exitTime, &kernelTime, &userTime ) != -1 )
	{
		SYSTEMTIME userSystemTime;
		if ( FileTimeToSystemTime( &userTime, &userSystemTime ) != -1 )
			return (double)userSystemTime.wHour * 3600.0 +
			(double)userSystemTime.wMinute * 60.0 +
			(double)userSystemTime.wSecond +
			(double)userSystemTime.wMilliseconds / 1000.0;
	}

#elif defined(__unix__) || defined(__unix) || defined(unix) || (defined(__APPLE__) && defined(__MACH__))
	/* AIX, BSD, Cygwin, HP-UX, Linux, OSX, and Solaris --------- */

#if defined(_POSIX_TIMERS) && (_POSIX_TIMERS > 0)
	/* Prefer high-res POSIX timers, when available. */
	{
		clockid_t id;
		struct timespec ts;
#if _POSIX_CPUTIME > 0
		/* Clock ids vary by OS.  Query the id, if possible. */
		if ( clock_getcpuclockid( 0, &id ) == -1 )
#endif
#if defined(CLOCK_PROCESS_CPUTIME_ID)
			/* Use known clock id for AIX, Linux, or Solaris. */
				id = CLOCK_PROCESS_CPUTIME_ID;
#elif defined(CLOCK_VIRTUAL)
			/* Use known clock id for BSD or HP-UX. */
				id = CLOCK_VIRTUAL;
#else
			id = (clockid_t)-1;
#endif
		if ( id != (clockid_t)-1 && clock_gettime( id, &ts ) != -1 )
			return (double)ts.tv_sec +
			(double)ts.tv_nsec / 1000000000.0;
	}
#endif

#if defined(RUSAGE_SELF)
	{
		struct rusage rusage;
		if ( getrusage( RUSAGE_SELF, &rusage ) != -1 )
			return (double)rusage.ru_utime.tv_sec +
			(double)rusage.ru_utime.tv_usec / 1000000.0;
	}
#endif

#if defined(_SC_CLK_TCK)
	{
		const double ticks = (double)sysconf( _SC_CLK_TCK );
		struct tms tms;
		if ( times( &tms ) != (clock_t)-1 )
			return (double)tms.tms_utime / ticks;
	}
#endif

#if defined(CLOCKS_PER_SEC)
	{
		clock_t cl = clock( );
		if ( cl != (clock_t)-1 )
			return (double)cl / (double)CLOCKS_PER_SEC;
	}
#endif

#endif

	return -1;		/* Failed. */
}

// resource usage. Records resource usage.
map < type, map < int, int > >resources;
vector < vector < int > * >  history_level_info;
// resource pool.
// Initialized when constructing from test case file.
map < type, int >resourcePool;
// operation pool.
// Initialized when constructing from test case file.
map < int, Operation * >operations;
// constraint pool.
// Initialized when constructing from test case file.
set < Dependency * >dependencies;
// container for current schedule
// Constructed on the fly.
map < Operation *, int >currentSchedule;
// container for best schedule sofar
// Constructed on the fly.
map < Operation *, int >optimalSchedule;
map < Operation *, int >badSchedule;
map < Operation *, int >listingSchedule;
map < Operation *, int >basicSchedule;
map < Operation *, int >lastFeasibleSchedule;
map < Operation *, int >CPofSubGraph;
map < Operation *, int >CPofSubGraph_;
map < Operation *, int >CPofPredGraph;
map < Operation *, int >CPofPredGraph_;
map < Operation *, int >CPofPreRevGraph;
map < Operation *, int >CPofPreRevGraph_;
map < Operation *, map < Operation *, int > >CPofNodes;
map < int, map < Operation *, int > >ASAPofMultiThread;
map < int, map < Operation *, int > >ALAPofMultiThread;
map < Operation *, int > ASAPUC;
map < Operation *, int > ALAPUC;
map < Operation *, set < Operation * > >immediatePrecedentOperations;
map < Operation *, set < Operation * > >successorOperations;
map < int, set < int > >level_l_h;
map <int, map<Operation *, bool> > precedenceRecord;
map<int, int> levelbound_info;
map<int, int> endofLevel; // end of cut now
// container for source operations
// not used
set < Operation * >sourceOperations;
multiset < Operation  > topoSet;
// container for sink operations
// not used
set < Operation* > sinkOperations;
multiset < Operation > sortedSetByALAP;
multiset < Operation > sortedSetByCP;
bool config_echo = false;
bool config_level = false;
bool config_low = false;
int maxOpTraversed = 0;
int globalLow = 0;
int new_low = 0;
bool terminateBB = false;
bool basicfound = false;
bool completeBranchBound = false;
int total_traverse = 0;
int total_duration = 0;
int core_limit = 16;
int environment_core_limit = 96;
int core_number = 0;
//HANDLE semephore;
int assignment = 0;
int count = 0;
//map < int, pthread_t > threadMap;
int latex_global;
int latex_optimal;
float latex_not_c;
float latex_not_t;
float latex_level_c;
float latex_level_t;
float latex_termi_c;
float latex_termi_t;
float latex_shrin_c;
float latex_shrin_t;
float latex_1p_c;
float latex_1p_t;
float latex_2p_c;
float latex_2p_t;
float latex_to_c;
float latex_to_t;
struct thread_ag
{
	int lower;
	int upper;
	int coreID;
	//	sem_t* assignmentSemaphore;//
	set < int > * assignmentMap;
};
struct search_ag
{
	int step;
	int op;
	int core;
	bool updateALAP;
	bool cpbound;
	bool levelbound;
	bool lowbound;
	bool preSearch;
	int * assignmentSemaphore; //
	set < int > * assignmentMap;
	search_strategy ss;
};
struct parallel_ag
{
	int assignmentSemaphore;//
	set<int> assignmentMap;
	int core_limit;
};
// variables for parallel algorithm
// need initializtion
map < int, map < Operation *, int > >currentSchedule_p;
map < int, map < Operation *, int > >optimalSchedule_p;
map < int, map < type, map < int, int > > > resources_p;
map < int, map < type, map < int, int > > > resource_snapshot_p;
int graph_count = 0;
// variables for parallel algorithm
fstream fout;
inline unsigned long long
	GetCycleCount()
{
	//__asm _emit 0x0F
	//__asm _emit 0x31
	return 0;
}
void
	floydWarshall()
{
	// init
	CPofNodes.clear();
	for( set < Dependency * >::const_iterator it =
		dependencies.begin(); it != dependencies.end(); it++ )
	{
		CPofNodes[( *it )->source][( *it )->sink] = ( *it )->source->delay;
	}
	for( int k = 1; k <= operations.size(); k++ )
	{
		for( int i = 1; i <= operations.size(); i++ )
		{
			for( int j = 1; j <= operations.size(); j++ )
			{
				// int test1 =
				// CPofNodes[operations[i]][operations[j]];
				// int test2 =
				// CPofNodes[operations[i]][operations[k]];
				// int test3 =
				// CPofNodes[operations[k]][operations[j]];
				if( CPofNodes[operations[i]][operations[k]] != 0
					&& CPofNodes[operations[k]][operations[j]] != 0 )
					CPofNodes[operations[i]][operations[j]] =
					max( CPofNodes[operations[i]][operations[j]],
					CPofNodes[operations[i]][operations[k]] +
					CPofNodes[operations[k]][operations[j]] );
			}
		}
	}
}
// for procedure "getSubGraph" find the sink ops of a specified op
void
	addSink( Operation * op, Graph * graph )
{
	if( op->adj.size() == 0 )
		return;
	for( set < Dependency * >::const_iterator it = op->adj.begin();
		it != op->adj.end(); it++ )
	{
		Dependency * dep = ( *it );
		graph->dependencies.insert( dep );
		graph->operations.insert( dep->sink );
		addSink( dep->sink, graph );
	}
}
// for procedure "getPrecedenceGraph" find the source op of a
// specified op
void
	addSource( Operation * op, Graph * graph, Graph * base )
{
	for( set < Dependency * >::const_iterator it =
		base->dependencies.begin(); it != base->dependencies.end();
		it++ )
	{
		Dependency * dep = ( *it );
		if( dep->sink == op )
		{
			graph->dependencies.insert( dep );
			graph->operations.insert( dep->source );
			addSource( dep->source, graph, base );
		}
	}
}
// for procedure "getPrecedenceGraph" find the source op of a
// specified op
void
	addSource( Operation * op, Graph * graph )
{
	for( set < Dependency * >::const_iterator it = dependencies.begin();
		it != dependencies.end(); it++ )
	{
		Dependency * dep = ( *it );
		if( dep->sink == op )
		{
			graph->dependencies.insert( dep );
			graph->operations.insert( dep->source );
			addSource( dep->source, graph );
		}
	}
}
// get sub graph
Graph * getSubGraph( Operation * op )
{
	Graph * rs = new Graph();
	// const Operation *curOp = op;
	rs->operations.insert( op );
	// get source recursively
	addSink( op, rs );
	rs->initGraph();
	return rs;
}
// get precedence graph
Graph * getPrecedenceGraph( Operation * op, Graph * base )
{
	Graph * rs = new Graph();
	// const Operation *curOp = op;
	rs->operations.insert( op );
	// get source recursively
	addSource( op, rs, base );
	rs->initGraph();
	return rs;
}
// get precedence graph
Graph * getPrecedenceGraph( Operation * op )
{
	Graph * rs = new Graph();
	// const Operation *curOp = op;
	rs->operations.insert( op );
	// get source recursively
	addSource( op, rs );
	rs->initGraph();
	return rs;
}
// get reversed graph
Graph * getReversedGraph( Graph * graph )
{
	Graph * rs = new Graph();
	rs->operations = graph->operations;
	for( set < Dependency * >::const_iterator it =
		graph->dependencies.begin(); it != graph->dependencies.end();
		it++ )
	{
		Dependency * dep1 = ( *it );
		Dependency * dep2 = new Dependency( dep1->sink, dep1->source );
		rs->dependencies.insert( dep2 );
	}
	rs->initGraph();
	return rs;
}
int
	getCriticalPathLength( Operation * op, Graph * g, enum cptype type )
{
	if( type == cpofsub )
	{
		/*   set < int >rs;
		for( set < Operation * >::const_iterator it =
		g->sourceOps.begin(); it != g->sourceOps.end(); it++ )
		{
		int depth = 0;
		Operation * op = ( *it );
		rs.insert( DFS( g, &rs, op, depth, type, false ) );
		}
		int len = *rs.rbegin();
		return len; */
		int rs = 0;
		for( set<Operation*>::iterator it = g->sinkOp.begin(); it != g->sinkOp.end(); it++ )
		{
			rs = max(rs, CPofNodes[op][*it]);
		}
		return rs;
	}
	else if( type == cpofsub_ )
	{
		set < int >rs;
		for( set < Operation * >::const_iterator it =
			g->sourceOps.begin(); it != g->sourceOps.end(); it++ )
		{
			int depth = 0;
			Operation * op = ( *it );
			rs.insert( DFS( g, &rs, op, depth, type, true ) );
		}
		int len = *rs.rbegin();
		return len;
	}
	else if( type == cpofpred )
	{
		/*    if( g->operations.size() == 1 )
		{
		Operation * op = *g->operations.begin();
		return 0;
		}
		else
		{
		int rs = 0;
		Operation * sink = operations[( *g->sinkOp.begin() )->id];
		for( set<Operation*>::const_iterator it = g->sourceOps.begin(); it != g->sourceOps.end(); it++ )
		rs = max( rs, CPofNodes[operations[( *it )->id]][operations[( *g->sinkOp.begin() )->id]] );
		return rs;
		}
		*/

		int rs = 0;
		for ( set<Operation*>::iterator it = g->sourceOps.begin(); it != g->sourceOps.end(); it++)
		{
			rs = max(rs, CPofNodes[*it][op]);
		}
		return rs;
	}
	else if( type == cpofpred_ )
	{
		if( g->operations.size() == 1 )
		{
			//Operation * op = *g->operations.begin();
			return 1;
		}
		else
		{
			Operation * source = *g->sourceOps.begin();
			Operation * sink = *g->sinkOp.begin();
			return source->CPSubGraph - sink->CPSubGraph;
		}
	}
	else if( type == cpofpredresv )
	{
		if( g->operations.size() == 1 )
		{
			Operation * op = *g->operations.begin();
			return op->delay;
		}
		else
		{
			Operation * source = *g->sourceOps.begin();
			Operation * sink = *g->sinkOp.begin();
			return sink->CPSubGraph - source->CPSubGraph + source->delay;
		}
	}

	return -1;
}
unsigned long long
	getEstimatedSpace()
{
	unsigned long long rs = 1;
	for( int i = 1; i <= operations.size(); i++ )
		rs *= ( operations[i]->ALAP - operations[i]->ASAP );
	return rs;
}
// DFS for CP calculation
int
	DFS( Graph * g, set < int >*rs, Operation * op, int depth,
	enum cptype type, bool isSimple )
{
	// printf( "DFS: processing op %d...\n", op->id );
	int *targetcp = NULL;
	switch( type )
	{
	case cpofsub:
		targetcp = &op->CPSubGraph;
		break;
	case cpofpred:
		targetcp = &op->CPPredGraph;
		break;
	case cpofpredresv:
		targetcp = &op->CPofPreRevGraph;
		break;
	}
	if( *targetcp != -1 && type == cpofsub )
		return *targetcp;
	bool hit = false;
	for( set < Dependency * >::const_iterator it =
		g->dependencies.begin(); it != g->dependencies.end(); it++ )
	{
		Dependency * dep = ( *it );
		if( dep->source == op )
		{
			*targetcp =
				max( op->delay + DFS( g, rs, dep->sink, depth, type, isSimple ),
				*targetcp );
			hit = true;
		}
	}
	if( !hit )
	{
		*targetcp = isSimple ? 1 : op->delay;
	}
	return *targetcp;
}
// DFS for level calculation
void
	DFS( Operation * op, int depth )
{
	// printf( "DFS Level: processing op %d...\n", op->id );
	if( op->visited )
		return;
	depth++;
	op->level = depth;
	level_l_h[depth].insert( op->id );
	if( op->adj.size() == 0 )
		return;
	for( set < Dependency * >::const_iterator it = op->adj.begin();
		it != op->adj.end(); it++ )
	{
		Dependency * dep = ( *it );
		// calculate level on the fly
		DFS( dep->sink, depth );
	}
	op->visited = true;
}
void topoSort()
{
	set< int > tempOp;
	level_l_h.clear();
	level_count = 0;
	for( map<int, Operation *>::const_iterator it = operations.begin(); it != operations.end(); it++ )
	{
		tempOp.insert( ( *it ).second->id );
	}
	int levelCount = 1;
	while( tempOp.size() != 0 )
	{
		set< int > tempOpSet;
		for( set < int >::const_iterator it =
			tempOp.begin(); it != tempOp.end(); it++ )
		{
			Operation * op = operations[ *it ];
			bool noIn = true;
			for( set < Dependency* >::const_iterator it2 = op->in.begin(); it2 != op->in.end(); it2++ )
			{
				Dependency * dep = *( it2 );
				if( tempOp.find( dep->source->id ) != tempOp.end() )
					noIn = false;
			}
			if( noIn )
				tempOpSet.insert( *it );
		}
		for( set<int>::const_iterator it = tempOpSet.begin(); it != tempOpSet.end(); it++ )
		{
			operations[*it]->level = levelCount;
			operations[*it]->sort_id = -levelCount;
			tempOp.erase( *it );
		}
		levelCount++;
		level_count = max( level_count, levelCount );
	}
	///////////added by mingsong
	//  for(int l=1; l<=levelCount; l++)
	//  {
	//   history_level_info[l] = new vector<int>();
	//}
	for( set < Dependency * >::const_iterator edge_it = dependencies.begin(); edge_it != dependencies.end(); edge_it++ )
	{
		int src = (*edge_it)->source->id;
		int dest = (*edge_it)->sink->id;
		int src_level = operations[src]->level;
		int dest_level = operations[dest]->level;

		for(int l=src_level; l<dest_level; l++)
			level_l_h[l].insert( src );
	}
	///////////////////////
	level_count--;
	for( map<int, Operation*>::const_iterator it = operations.begin(); it != operations.end(); it++ )
	{
		topoSet.insert( *( *it ).second );
	}
}
void
	initASAP()
{
	for( map < int, Operation * >::const_iterator it =
		operations.begin(); it != operations.end(); it++ )
	{
		Operation * op = ( *it ).second;
		op->ASAP = CPofPredGraph[op] + 1;
	}
}
void
	initALAP()
{
	for( map < int, Operation * >::const_iterator it =
		operations.begin(); it != operations.end(); it++ )
	{
		Operation * op = ( *it ).second;
		//  printf("op%d cp sub pre prerev %d %d %d\n", op->id, CPofSubGraph[op], CPofPredGraph[op], CPofPreRevGraph[op]);
		op->ALAP = w - CPofSubGraph[op];
	}
}
void
	printCurrentSchedule( int i )
{
	// fout << "current schedule:
	for( int j = 1; j <= i; j++ )
	{
		printf( "%d %%%.0f ", currentSchedule[operations[j]],
			( currentSchedule[operations[j]] - operations[j]->ASAP +
			1.0 ) / ( operations[j]->ALAP - operations[j]->ASAP +
			1.0 ) * 100 );
		// fout << currentSchedule[operations[j]];
	}
	// fout <<"\n";
	printf( "\n" );
}
void
	printCurrentSchedule( int core, int i )
{
	// fout << "current schedule:
	printf( "thread %d: ", core );
	for( int j = 1; j <= i; j++ )
	{
		printf( "%d ", currentSchedule_p[core][operations[j]->sortedOp] );
		//( currentSchedule_p[core][operations[j]] -
		// operations[j]->ASAP + 1.0 ) / ( operations[j]->ALAP -
		//                                operations[j]->ASAP +
		//                                1.0 ) * 100 );
		// fout << currentSchedule[operations[j]];
	}
	// fout <<"\n";
	printf( "\n" );
}
void
	writeSchedule( char *info )
{
	fout << info << "writesche(): found a schedule:\n";
	for( int j = 1; j <= operations.size(); j++ )
	{
		fout << currentSchedule[operations[j]] << "\t" <<
			operations[j]->ASAP << "\t" << operations[j]->ALAP << "\n";
	}
	fout << "\n";
	fout.flush();
}
void
	writeSchedule( int core )
{
	fout << "found a schedule at thread " << core << " ";
	for( int j = 1; j <= operations.size(); j++ )
	{
		fout << currentSchedule_p[core][operations[j]] << " ";
	}
	fout << "\n";
	fout.flush();
}
void
	saveASAP()
{
	for( int i = 1; i <= operations.size(); i++ )
	{
		// tempASAP[operations[i]] = operations[i]->ASAP;
	}
}
void
	restoreASAP()
{
	for( int i = 1; i <= operations.size(); i++ )
	{
		// operations[i]->ASAP = tempASAP[operations[i]];
	}
}
bool CPBound( Operation * op )
{
	bool rs = true;
	FuncTimer::checkin( cpbound_t );
	int l = *level_l_h[op->level].begin();
	int h = *level_l_h[op->level].rbegin();
	for( int i = l; i <= h; i++ )
	{
		Operation * opi = operations[i];
		rs =
			rs & ( currentSchedule[op] + CPofSubGraph[op] >=
			optimalSchedule[opi] + CPofSubGraph[opi] );
	}
	FuncTimer::checkout( cpbound_t );
	return rs;
}
bool CPBound( int core, Operation * op )
{
	bool rs = true;
	int l = *level_l_h[op->level].begin();
	int h = *level_l_h[op->level].rbegin();
	for( int i = l; i <= h; i++ )
	{
		Operation * opi = operations[i];
		rs =
			rs & ( currentSchedule_p[core][op] + CPofSubGraph[op] >=
			optimalSchedule_p[core][opi] + CPofSubGraph[opi] );
	}
	return rs;
}
void
	branchBoundRCS_h( int i )
{
	if( i == operations.size() + 1 )
	{
		if( optimalScheduleTime > calculateMaxScheduleTime() )
		{
			optimalSchedule = currentSchedule;
			optimalScheduleTime = calculateMaxScheduleTime();
		}
	}
	else
	{
		Operation * op = operations[i];
		for( int step = op->ASAP; step <= op->ALAP; step++ )
		{
			map < Operation *, int >tempASAP;
			// save ASAP
			for( int i = 1; i <= operations.size(); i++ )
				tempASAP[operations[i]] = operations[i]->ASAP;
			if( isResourceAvailable( step, op->t, op->delay ) )
			{
				int l = lowBound( op );
				int u = upperBound( op );
				if( u < optimalScheduleTime )
				{
				}
			}
		}
	}
}
// main HLS algorithm +
void
	branchBoundRCS( int i, bool update, bool bCPbound, bool blevelBound )
{
	total_traverse++;
	maxOpTraversed = max( maxOpTraversed, i );
	// printf( "branchBoundRCS: processing op %d...\n", i );
	if( i <= operations.size() )
	{
		Operation * op = operations[i];
		for( int step = op->ASAP; step <= op->ALAP; step++ )
		{
			map < Operation *, int >tempASAP;
			// save ASAP
			for( int i = 1; i <= operations.size(); i++ )
				tempASAP[operations[i]] = operations[i]->ASAP;
			// pass step as step into isPrecedence &
			// isResourceAvailable
			if(	// isPrecedence( op, step ) &&
				isResourceAvailable( step, op->t, op->delay ) )
			{
				currentSchedule[op] = step;
				if( i <= 4 )
					printCurrentSchedule( i );
				// //todo: justify
				if( bCPbound && CPBound( op ) )
					return;
				if( blevelBound && levelBound( op ) )
					return;
				// if( bTOPObound && topoBound( op ) )
				// continue;
				if(	// !blowbound ||
					lowBound( op ) < optimalScheduleTime )
				{
					occupyResource( step, op->t, op->delay );
					updateASAP( op, step );
					if( update )
					{
						updateALAP( op );
					}
					branchBoundRCS( i + 1, update, bCPbound,
						blevelBound );
					releaseResource( step, op->t, op->delay );
				}
				else
				{
					// printf( "*" );
					// fout << "omit from lowbound at op " << op->id
					// << " at level " << op->level << "\n";
					// printf( "return from low bound at " );
					// printCurrentSchedule( i );
					continue;
				}
			}
			for( int i = 1; i <= operations.size(); i++ )
				operations[i]->ASAP = tempASAP[operations[i]];
		}
	}
	else
	{
		completeBranchBound = true;
		int scheduleTime = calculateMaxScheduleTime();
		printf( "bb: found a schedule: %d ", scheduleTime );
		lastFeasibleSchedule = currentSchedule;
		for( int i = 1; i <= operations.size(); i++ )
			printf( "%d", currentSchedule[operations[i]] );
		printf( "\n" );
		fout << "bb: found a shcedule\n";
		writeSchedule( "Found by BB" );
		fout.flush();
		if( optimalScheduleTime >= scheduleTime )
		{
			completeBranchBound = true;
			optimalScheduleTime = scheduleTime;
			optimalSchedule = currentSchedule;
			// update alap
			// printf( "found update!\n" );
			// for( int k = 1; k <= operations.size(); k++ )
			// {
			// Operation * opk = operations[k];
			// opk->ALAP = min( opk->ALAP, optimalScheduleTime -
			// CPofPreRevGraph[opk] + 1 );
			// }
		}
	}
}
void
	coreScheduler( void *arg )
{
	thread_ag * ta = ( thread_ag * ) arg;
	int current = ta->lower;
	//	pthread_t coreThread;//
	while( current <= ta->upper )
	{
		search_ag * sa = ( search_ag * ) malloc( sizeof( search_ag ) );
		sa->core = ta->coreID;
		sa->op = 1;
		sa->step = current;

		sa->updateALAP = true;
		sa->preSearch = false;
		sa->lowbound = true;
		sa->levelbound = false;

		// WaitForSingleObject( *ta->assignmentSemaphore, 0L );
		//	sem_wait(ta->assignmentSemaphore);
		if( ta->assignmentMap->find( current ) == ta->assignmentMap->end() )
		{
			current++;
			free( sa );
			//  ReleaseSemaphore( *ta->assignmentSemaphore, 1, NULL );
			//		sem_post(ta->assignmentSemaphore);
			//sem_post( ta->assignmentSemaphore );
			continue;
		}
		ta->assignmentMap->erase( current );
		//ReleaseSemaphore( *ta->assignmentSemaphore, 1, NULL );
		//	sem_post( ta->assignmentSemaphore );
		//coreThread = ( int )_beginthread( branchBoundRCS_thread, 0, ( void* )sa );//
		printf("core_scheduler: start task at %d on core %d\n", sa->step, ta->coreID);
		//		pthread_create(&coreThread, NULL, (void*(*)(void*))branchBoundRCS_thread, (void*)sa);

		//SetThreadAffinityMask (coreThread, (DWORD_PTR) ta->coreID);
		// SetThreadPriority( coreThread, THREAD_PRIORITY_HIGHEST );
		//WaitForSingleObject( coreThread, INFINITE );
		//	pthread_join( coreThread, NULL );
		printf("core_scheduler: finished task at %d on core %d\n", sa->step, ta->coreID);

		free( sa );
		current++;
	}
	//WaitForSingleObject( *ta->assignmentSemaphore, 0L );
	//	sem_wait( ta->assignmentSemaphore );
	int remain = ta->assignmentMap->size();
	while( remain != 0 )
	{
		search_ag * sa = ( search_ag * ) malloc( sizeof( search_ag ) );
		sa->core = ta->coreID;
		sa->op = 1;
		sa->step = *ta->assignmentMap->begin();

		sa->updateALAP = true;
		sa->preSearch = false;
		sa->lowbound = true;
		sa->levelbound = false;

		ta->assignmentMap->erase( sa->step );
		//ReleaseSemaphore( *ta->assignmentSemaphore, 1, NULL );
		//	sem_post( ta->assignmentSemaphore );
		// coreThread = ( int )_beginthread( branchBoundRCS_thread, 0, ( void* )sa );//
		//     pthread_attr_setschedparam(<#pthread_attr_t *#>, <#const struct sched_param *#>)
		//SetThreadAffinityMask (coreThread, (DWORD_PTR) ta->coreID);
		//	pthread_attr_t attr;
		//	sched_param param;
		int newprio=99;
		//	pthread_attr_init(&attr);
		//	pthread_attr_getschedparam(&attr, &param);
		//	param.sched_priority = newprio;
		//	pthread_attr_setschedparam(&attr, &param);
		printf("core_scheduler: start task at %d on core %d\n", sa->step, ta->coreID);

		//	pthread_create( &coreThread, &attr, (void*(*)(void*))branchBoundRCS_thread, ( void*) sa );

		//     pthread_setaffinity_np();
		// SetThreadPriority( coreThread, THREAD_PRIORITY_HIGHEST );
		//WaitForSingleObject( coreThread, INFINITE );

		//	pthread_join( coreThread, NULL );
		printf("core_scheduler: finished task at %d on core %d\n", sa->step, ta->coreID);

		free( sa );
		//WaitForSingleObject( *ta->assignmentSemaphore, 0L );
		//	sem_wait( ta->assignmentSemaphore );
		remain = ta->assignmentMap->size();
	}
	//ReleaseSemaphore( *ta->assignmentSemaphore, 1, NULL );
	//	sem_post( ta->assignmentSemaphore );
}
void
	printInfo( char *str )
{
	printf( str );
	printf( "\n" );
	fout << str << "\n";
	//fout.flush();
}
void
	testDriver( char *info, bool shrink, bool lowbound, bool level, bool twophase )
{
	fout << "\nshrink: " << shrink << " termination: " << lowbound << " level: " << level << " two-phase: " << twophase << "\n";
	resetContext();
	printInfo( "\n" );
	printInfo( info );
	search_ag * sa = ( search_ag * ) malloc( sizeof( search_ag ) );
	sa->core = 1;
	sa->op = 1;
	sa->step = -1;
	sa->updateALAP = shrink;
	sa->preSearch = twophase;
	sa->levelbound = level;
	sa->lowbound = lowbound;
	printInfo( "pre-search...\n" );
	updateALAP( 1, NULL, shrink );
	double start = 0;
	double end = 0;
	if( twophase )
	{
		start = dGetTickCount();
		currentSchedule_p[1].clear();
		branchBoundRCS_thread( sa );
		end = dGetTickCount();
		fout << "pre-search total duration: " << end - start << "\n";
		latex_1p_c = total_traverse;
		latex_1p_t = end - start;
	}
	fout << "pre traverse: " << total_traverse << "\n";
	total_traverse = 0;
	sa->preSearch = false;
	printInfo( "formal-search...\n" );
	start = dGetTickCount();
	currentSchedule_p[1].clear();
	branchBoundRCS_thread( sa );
	end = dGetTickCount();
	printInfo( info );
	latex_optimal = optimalScheduleTime;
	fout << "The optimal schedule time is " << optimalScheduleTime <<
		"\n";
	for( int i = 1; i <= operations.size(); i++ )
	{
		Operation * op = operations[i];
		fout << op->id << "\t" << optimalSchedule_p[1][op] << "\n";
	}
	fout << "Finished branchbound? " << completeBranchBound << "\n";
	total_duration = end - start;
	fout << "total duration: " << end - start << "\n";
	fout << "total traverse: " << total_traverse << "\n";
	fout << "max op traversed: " << maxOpTraversed << "\n";
	for( int i = 1; i <= FuncTimer::tickets.size(); i++ )
	{
		fout << i << " " << FuncTimer::tickets[( func_type ) i] << " " <<
			FuncTimer::times[( func_type ) i] << "\n";
	}
	fout.flush();
}
// main HLS algorithm +
void
	branchBoundRCS_thread( void *arg )
{
	search_ag * sa = ( search_ag * ) arg;
	int i = sa->op;
	int core = sa->core;
	if( i == 1 && sa->preSearch )
	{
		printf( "init low: %d\n", globalLow );
	}

	maxOpTraversed = max( maxOpTraversed, i );
	if( i <= operations.size() )
	{
		Operation * op = operations[i]->sortedOp;
		int start_step;
		int end_step;
		if( sa->step == -1 )
		{
			//start_step = min(ASAPofMultiThread[core][op], ASAPUC[op]);
			start_step = ASAPofMultiThread[core][op];
			end_step = ALAPofMultiThread[core][op];
		}
		else
		{
			start_step = sa->step;
			end_step = sa->step;
		}
		for( int step = start_step; step <= end_step; step++ )
		{
			if( sa->lowbound && optimalScheduleTime == globalLow )
			{
				printInfo( "lower bound == upper bound, terminate\n" );
				return;
			}
			else if( optimalScheduleTime < globalLow )
			{
				printInfo( "upper < low error!\n" );
				return;
			}

			total_traverse++;
			if( sa->lowbound && optimalScheduleTime <= globalLow )
			{
				return;
			}
			int low = 0;
			map < Operation *, int >tempASAP;
			// save ASAP
			for( int i = 1; i <= operations.size(); i++ )
				tempASAP[operations[i]] = ASAPofMultiThread[core][operations[i]];
			// pass step as step into isPrecedence &
			// isResourceAvailable
			if(// isPrecedence( core, op, step ) &&
				isResourceAvailable( core, step, op->t, op->delay ) )
			{

				//            if( i <= 2 )
				//if( config_echo )
				//if (i <= 4)
				//   printCurrentSchedule (core, i);
				// todo: justify/
				//        if( sa->cpbound && CPBound( core, op ) )
				{
					// printf("CP hint\n");
					//        return;
				}
				//               if( ( !sa->preSearch && sa->levelbound  && levelBound( core, op, step ) ) )
				{
					// printf( "return from level bound at " );
					// printCurrentSchedule( i );
					// printf( "terminatebb at op %d at level %d\n",
					// i, op->level );
					// terminateBB = true;
					//                  if( config_echo )
					//                       fout << "return from levelbound at op " <<
					//                           op->id << " at level " << op->level << "\n";
					// printf("LEVEL hint\n");
					//                   return;
					//
				}


				low = lowBound( core, operations[sa->op] );
				updateALAP( core, operations[sa->op], sa->updateALAP );

				low = 0;

				if( low < optimalScheduleTime )
				{
					//printf("currentSchedule_p[%d][%d] = %d\n", sa->core, op->id, step);
					currentSchedule_p[sa->core][op] = step;
					// printCurrentSchedule( sa->core, i );


					occupyResource( core, step, op->t, op->delay );


					updateASAP( core, op, step );

					search_ag * sa2 =
						( search_ag * ) malloc( sizeof( search_ag ) );
					sa2->op = i + 1;
					sa2->step = -1;
					sa2->core = core;
					sa2->updateALAP = sa->updateALAP;
					sa2->cpbound = sa->cpbound;
					sa2->preSearch = sa->preSearch;
					sa2->lowbound = sa->lowbound;
					sa2->levelbound = sa->levelbound;
					sa2->updateALAP = sa->updateALAP;
					if( ( op->id != endofLevel[op->level] && sa->preSearch ) || !sa->preSearch )
					{

						branchBoundRCS_thread( ( void * )( sa2 ) );
					}
					free( sa2 );
					releaseResource( core, step, op->t, op->delay );
				}
				else
				{
					if( config_echo )
						fout << "omit from lowbound at op " << op->id
						<< " at level " << op->level << "\n";
					continue;
				}
			}
			// restore ASAP
			for( int i = 1; i <= operations.size(); i++ )
				ASAPofMultiThread[core][operations[i]] =
				tempASAP[operations[i]];
		}
	}
	else
	{
		completeBranchBound = true;
		int scheduleTime = calculateMaxScheduleTime( core );
		char str[256];
		//       sprintf( str, "bb: else: found a schedule: %d\n", scheduleTime );
		//       printInfo( str );
		lastFeasibleSchedule = currentSchedule_p[core];
		//       for( int i = 1; i <= operations.size(); i++ )
		//           printf( "%d", currentSchedule_p[core][operations[i]] );
		//       writeSchedule( core );
		//       fout.flush();
		if( optimalScheduleTime >= scheduleTime )
		{
			completeBranchBound = true;
			optimalScheduleTime = scheduleTime;
			optimalSchedule_p[core] = currentSchedule_p[core];
			resource_snapshot_p[core] = resources_p[core];
			//added by mingsong
			//   for(int i=1; i<=level_count; i++)
			{
				vector<int> * newS= new vector<int>();
				newS->push_back(0);
				history_level_info.push_back(newS );
				for( int i = 1; i <= operations.size(); i++ )
					newS->push_back( currentSchedule_p[core][operations[i]] );

				//	for(  set < int >::const_iterator set_it = level_l_h[i].begin(); set_it != level_l_h[i].end(); set_it++   )
				//	history_level_info[i]->back()->push_back(currentSchedule[operations[*set_it]] );

			}
		}
	}
}
// main HLS algorithm +
void
	basicEnu( int i )
{
	if( basicfound )
		return;
	if( i <= operations.size() )
	{
		Operation * op = operations[i];
		int step = op->ASAP;
		// for( int step = op->ASAP; step <= op->ALAP; step++ )
		while( true )
		{
			// pass step as step into isPrecedence &
			// isResourceAvailable
			if( isPrecedence( op, step )
				&& isResourceAvailable( step, op->t, op->delay ) )
			{
				if( basicfound )
					return;
				currentSchedule[op] = basicSchedule[op] = step;
				occupyResource( step, op->t, op->delay );
				basicEnu( i + 1 );
				releaseResource( step, op->t, op->delay );
			}
			step++;
		}
	}
	else
	{
		printf( "basicEnu: found a schedule... %d\n",
			calculateMaxScheduleTime() );
		completeBranchBound = true;
		int scheduleTime = calculateMaxScheduleTime();
		if( scheduleTime <= basicSchedulingTime )
		{
			basicSchedulingTime = scheduleTime;
			fout << "initial basic schedule: " << scheduleTime << "\n";
			writeSchedule( "Found by Basic" );
		}
		optimalScheduleTime = w = min( w, basicSchedulingTime );
		basicfound = true;
		return;
	}
}
// evaluate all schedules and pick the max value +
int
	calculateMaxScheduleTime()
{
	int current_schedule_time = 0;
	int temp = 0;
	for( int i = 1; i <= operations.size(); i++ )
	{
		temp = currentSchedule[operations[i]] + operations[i]->delay - 1;
		current_schedule_time = max( current_schedule_time, temp );
	}
	return current_schedule_time;
}
int
	calculateMaxScheduleTime( int core )
{
	int current_schedule_time = 0;
	int temp = 0;
	for( int i = 1; i <= operations.size(); i++ )
	{
		temp =
			currentSchedule_p[core][operations[i]] + operations[i]->delay - 1;
		current_schedule_time = max( current_schedule_time, temp );
	}
	return current_schedule_time;
}
// occupy resource of specified type
void
	occupyResource( int step, type t, int delay )
{
	FuncTimer::checkin( occupyResource_t );
	for( int i = step; i < step + delay; i++ )
	{
		// occupy the resource for subsequent steps
		resources[t][i]++;
	}
	FuncTimer::checkout( occupyResource_t );
}
void
	occupyResource( int core, int step, type t, int delay )
{
	FuncTimer::checkin( occupyResource_t );
	for( int i = step; i < step + delay; i++ )
	{
		// occupy the resource for subsequent steps
		resources_p[core][t][i]++;
	}
	FuncTimer::checkout( occupyResource_t );
}
// release resource of specified type
void
	releaseResource( int step, type t, int delay )
{
	FuncTimer::checkin( releaseResource_t );
	for( int i = step; i < step + delay; i++ )
	{
		// release the resource for subsequent steps
		resources[t][i]--;
	}
	FuncTimer::checkout( releaseResource_t );
}
void
	releaseResource( int core, int step, type t, int delay )
{
	FuncTimer::checkin( releaseResource_t );
	for( int i = step; i < step + delay; i++ )
	{
		// release the resource for subsequent steps
		resources_p[core][t][i]--;
	}
	FuncTimer::checkout( releaseResource_t );
}
void
	updateASAP( Operation * op, int step )
{
	FuncTimer::checkin( updateasap_t );
	for( set < Operation * >::const_iterator it =
		successorOperations[op].begin();
		it != successorOperations[op].end(); it++ )
	{
		if( ( *it )->ASAP < step + CPofNodes[op][( *it )] )
		{
			// printf( "updateASAP: updated op%d from %d to %d!\n", (
			// *it )->id, ( *it )->ASAP, step + CPofNodes[op][( *it )]
			// );
			// fout << "updateASAP: updated op" << ( *it )->id << "
			// from " << ( *it )->ASAP << "to " << step +
			// CPofNodes[op][( *it )] << "!\n";
			( *it )->ASAP = max( ( *it )->ASAP, step + CPofNodes[op][( *it )] );	// todo:
			// cp
			// between
			// opi
			// and
			// opj
		}
	}
	FuncTimer::checkout( updateasap_t );
}
void
	updateASAP( int core, Operation * op, int step )
{
	FuncTimer::checkin( updateasap_t );
	for( set < Operation * >::const_iterator it =
		successorOperations[op].begin();
		it != successorOperations[op].end(); it++ )
	{
		if( ASAPofMultiThread[core][( *it )] <
			step + CPofNodes[op][( *it )] )
		{
			// printf( "updateASAP: updated op%d from %d to %d!\n", (
			// *it )->id, ( *it )->ASAP, step + CPofNodes[op][( *it )]
			// );
			// fout << "updateASAP: updated op" << ( *it )->id << "
			// from " << ( *it )->ASAP << "to " << step +
			// CPofNodes[op][( *it )] << "!\n";
			ASAPofMultiThread[core][( *it )] = max( ASAPofMultiThread[core][( *it )], step + CPofNodes[op][( *it )] );	// todo:
			// ASAPofMultiThread[core][( *it )] = min( ASAPofMultiThread[core][( *it )], ASAPUC[op]);
			// cp
			// between
			// opi
			// and
			// opj
		}
	}
	FuncTimer::checkout( updateasap_t );
}
void
	updateALAP( Operation * op )
{
	// if( op->id == 27 )
	// int test = 0;
	if( op->id == operations.size() )
		return;
	FuncTimer::checkin( updateALAP_t );
	map < type, map < int, int > >resources_ = resources;
	map < Operation *, int >tempSchedule = currentSchedule;
	multiset < Operation > L_;
	map < int, int >L_array;
	map < int, int >S_;
	int w_ = 0;
	for( int i = 1; i <= op->id; i++ )
	{
		S_[i] = currentSchedule[operations[i]];
	}
	for( int i = op->id + 1; i <= operations.size(); i++ )
	{
		operations[i]->sort_id = -operations[i]->ALAP;
		L_.insert( *operations[i] );
	}
	int count = 1;
	for( multiset < Operation >::iterator it = L_.begin();
		it != L_.end(); it++ )
	{
		L_array[count] = ( *it ).id;
		count++;
	}
	for( int k = 1; k <= operations.size() - op->id; k++ )
	{
		Operation * opk = operations[L_array[k]];
		// todo: opi or opk?
		// note: opk is input for single
		int j = 1;
		while( true )
		{
			if( isPrecedence( opk, j )
				&& isResourceAvailable( j, opk->t, opk->delay ) )
			{
				// only occupy, no release is needed
				occupyResource( j, opk->t, opk->delay );
				S_[opk->id] = j;
				currentSchedule[opk] = j;
				break;
			}
			j++;
		}
	}
	for( int l = 1; l <= operations.size() - op->id; l++ )
	{
		Operation * op = operations[L_array[l]];
		if( S_[op->id] == 0 )
			continue;
		w_ = max( S_[op->id] + op->delay, w_ );
	}
	if( w_ == 0 )
		return;
	// printf( "w_:w %d:%d!\n", w_, w );
	// todo: how to update w
	if( w_ < optimalScheduleTime )
	{
		printf( "updateALAP: updated from %d to %d!\n",
			optimalScheduleTime, w_ );
		fout << "updateALAP: updated from " << optimalScheduleTime <<
			" to " << w_ << "!\n";
		for( int k = 1; k <= operations.size(); k++ )
		{
			Operation * opk = operations[k];
			opk->ALAP = w_ - CPofSubGraph[opk];
		}
		writeSchedule( "Update by UpdateALAP" );
		w = optimalScheduleTime = w_;
		optimalSchedule = currentSchedule;
	}
	// restore resource usage pool
	resources = resources_;
	currentSchedule = tempSchedule;
	FuncTimer::checkout( updateALAP_t );
}
void
	updateALAP( int core, Operation * op, bool shrink )
{
	//  printf("op11 has step:%d\n", ASAPofMultiThread[core][operations[11]]);
	// if( op->id == 27 )
	// int test = 0;
	int endid = ( op == NULL ) ? 0 : op->id - 1;
	if( endid == operations.size() )
		return;
	map < type, map < int, int > >resources_ = resources_p[core];
	map < Operation *, int >tempSchedule = currentSchedule_p[core];
	multiset < Operation > L_;
	map < int, int >L_array;
	map < int, int >S_;
	int w_ = 0;
	for( int i = 1; i <= endid; i++ )
		S_[i] = currentSchedule_p[core][operations[i]->sortedOp];
	for( int i = endid + 1; i <= operations.size(); i++ )
	{
		//     operations[i]->sortedOp->sort_id = -operations[i]->sortedOp->ALAP ;
		switch (global_listorder) {
		case byasap:
			operations[i]->sortedOp->sort_id = -operations[i]->sortedOp->ASAP;
			break;
		case byalap:
			operations[i]->sortedOp->sort_id = -operations[i]->sortedOp->ALAP;
			break;

		default:
			break;
		}        L_.insert( *operations[i]->sortedOp );
	}
	int count = 1;
	for( multiset < Operation >::iterator it = L_.begin();
		it != L_.end(); it++ )
	{
		L_array[count] = ( *it ).id;
		count++;
	}
	for( int k = 1; k <= operations.size() - endid; k++ )
	{
		Operation * opk = operations[L_array[k]];
		// todo: opi or opk?
		// note: opk is input for single
		int j = ASAPofMultiThread[core][opk];
		while( true )
		{
			if( isPrecedence( core, opk, j )
				&& isResourceAvailable( core, j, opk->t, opk->delay ) )
			{
				// only occupy, no release is needed
				occupyResource( core, j, opk->t, opk->delay );
				S_[opk->id] = j;
				currentSchedule_p[core][opk] = j;
				break;
			}
			j++;
		}
	}
	for( int l = 1; l <= operations.size(); l++ )
	{
		Operation * op = operations[l];
		//       if( S_[op->id] == 0 )
		//           continue;
		w_ = max( currentSchedule_p[core][op] + op->delay - 1, w_ );
	}
	if( w_ == 0 )
		return;
	// printf( "w_:w %d:%d!\n", w_, w );
	// todo: how to update w
	if( w_ < optimalScheduleTime )
	{
		char str[256];
		sprintf_s( str, "updateALAP: upper bound updated from %d to %d at core %d at op %d!",
			optimalScheduleTime, w_, core, ( op == NULL ? 0 : op->sortedOp->id ) );
		//    if( config_echo )
		printInfo( str );
		if( shrink )
		{
			for( int l = 1; l <= core_number; l++)
			{
				for( int k = 1; k <= operations.size(); k++ )
				{
					Operation * opk = operations[k];
					ALAPofMultiThread[core_number][opk] = opk->ALAP = min(ALAPofMultiThread[core_number][opk], w_ - CPofSubGraph[opk]);
					sprintf_s( str, "updateALAP: op %d update to %d at core %d at op %d!",
						k, ALAPofMultiThread[core][opk], core, ( op == NULL ? 0 : op->sortedOp->id ) );
					if( config_echo )
						printInfo( str );
				}
			}
		}
		w = optimalScheduleTime = min(optimalScheduleTime, w_);
		optimalSchedule_p[core] = currentSchedule_p[core];
		printf("op11 has step:%d\n", optimalSchedule_p[core][operations[11]]);
		resource_snapshot_p[core] = resources_p[core];
		//   for(int i=1; i<=level_count; i++)
		//	   {
		//		history_level_info[i]->push_back(new vector<int> ());
		//
		// 	for(  set < int >::const_iterator set_it = level_l_h[i].begin(); set_it != level_l_h[i].end(); set_it++   )
		//	history_level_info[i]->back()->push_back(currentSchedule_p[core][operations[*set_it]] );
		//
		//	   }
		{
			vector<int> * newS= new vector<int>();
			newS->push_back(0);
			history_level_info.push_back(newS );
			for( int i = 1; i <= operations.size(); i++ )
				newS->push_back( currentSchedule_p[core][operations[i]] );

			//	for(  set < int >::const_iterator set_it = level_l_h[i].begin(); set_it != level_l_h[i].end(); set_it++   )
			//	history_level_info[i]->back()->push_back(currentSchedule[operations[*set_it]] );

		}
		/*
		for( int i = 1; i <= level_count; i++ )
		{
		map<int, int> maxLow;
		for( set < int >::const_iterator it = level_l_h[i].begin();
		it != level_l_h[i].end(); it++ )
		{
		maxLow[operations[*it]->graph] =
		max( maxLow[operations[*it]->graph],
		optimalSchedule_p[core][operations[*it]] +
		CPofSubGraph[operations[*it]] );
		}
		for( set < int >::const_iterator it =
		level_l_h[i].begin(); it != level_l_h[i].end();
		it++ )
		{
		operations[*it]->ALAP =
		min( operations[*it]->ALAP,
		maxLow[operations[*it]->graph] - CPofPreRevGraph[operations[*it]] + 1 );
		}
		}
		*/
	}
	// restore resource usage pool
	resources_p[core] = resources_;
	currentSchedule_p[core] = tempSchedule;
	//	globalLow = max(globalLow, NULL);
}
//
bool levelBound( Operation * op )
{
	// if( op->id == 28 )
	// {
	// int test = 0;
	// }
	FuncTimer::checkin( levelbound_t );
	int l = *level_l_h[op->level].begin();
	int h = *level_l_h[op->level].rbegin();
	printf("level %d, %d \n", l , h);
	// getLhHh( &l, &h, op );
	bool temp_bool = true;
	if( op->id != h )
	{
		FuncTimer::checkout( levelbound_t );
		return false;
	}
	if( op->id == h )
	{//map < int, set < int > >level_l_h;
		//      for( int i = l; i <= h; i++ )
		for(  set < int >::const_iterator set_it = level_l_h[op->level].begin(); set_it != level_l_h[op->level].end(); set_it++   )
			temp_bool = temp_bool &
			( currentSchedule[operations[*set_it]] >= optimalSchedule[operations[*set_it]] );	// ||
		if(temp_bool){printf("hit level\n"); return true;}
		for(int iteration =0; iteration < history_level_info.size(); iteration++)
		{
			if(temp_bool){printf("compare history %d \n", iteration+1); }
			temp_bool = true;
			for(  set < int >::const_iterator set_it = level_l_h[op->level].begin(); set_it != level_l_h[op->level].end(); set_it++   )
			{
				temp_bool = temp_bool &
					( currentSchedule[operations[*set_it]] >= history_level_info[iteration]->at(*set_it));
			}
			//	for( int i = l; i <= h; i++,ind++ )
			//		temp_bool = temp_bool &
			//			( currentSchedule[operations[i]] >= (history_level_info[op->level]->at(iteration))->at(ind));
			if(temp_bool){ return true;}
		}

		/*
		* for( int i = l; i <= op->id - 1; i++ )
		if( (
		* currentSchedule[op] > currentSchedule[operations[i]] &&
		* CPofSubGraph[op] > CPofSubGraph[operations[i]] && op->t ==
		* operations[i]->t ) ||
		( currentSchedule[op] <
		* currentSchedule[operations[i]] && CPofSubGraph[op] <
		* CPofSubGraph[operations[i]] && op->t == operations[i]->t )
		* )
		{
		FuncTimer::checkout( levelbound_t );
		return true;
		* }
		*/
		FuncTimer::checkout( levelbound_t );

		//   return temp_bool;
	}
	/*
	*
	for( int i = l; i <= op->id - 1; i++ )
	if( (
	* currentSchedule[op] > currentSchedule[operations[i]] &&
	* CPofSubGraph[op] > CPofSubGraph[operations[i]] && op->t ==
	* operations[i]->t ) ||
	( currentSchedule[op] <
	* currentSchedule[operations[i]] && CPofSubGraph[op] <
	* CPofSubGraph[operations[i]] && op->t == operations[i]->t ) )
	* {
	FuncTimer::checkout( levelbound_t );
	return true;
	}
	//(
	* currentSchedule[op] + CPofSubGraph[op] >= optimalScheduleTime
	* );
	FuncTimer::checkout( levelbound_t );
	return false;
	* if( temp_bool )
	return true;
	else
	return false;
	*/
	return false;
}
bool topoBound( Operation * op )
{
	int l = *level_l_h[op->level].begin();
	int h = *level_l_h[op->level].rbegin();
	for( int i = l; i <= op->id - 1; i++ )
		if( ( currentSchedule[op] > currentSchedule[operations[i]]
		&& CPofSubGraph[op] > CPofSubGraph[operations[i]]
		&& op->t == operations[i]->t )
			||
			( currentSchedule[op] < currentSchedule[operations[i]]
		&& CPofSubGraph[op] < CPofSubGraph[operations[i]]
		&& op->t == operations[i]->t ) )
		{
			return true;
		}
		return false;
}
bool levelBound( int core, Operation * op, int step )
{
	bool temp_bool = true;
	bool  a_res = true;
	bool m_res = true;
	if( op->id != endofLevel[op->level] )
		return false;
	else
	{
		for( set<int>::const_iterator it = level_l_h[op->level].begin(); it != level_l_h[op->level].end(); it++ )
			temp_bool = temp_bool &
			( currentSchedule_p[core][operations[*it]] > optimalSchedule_p[core][operations[*it]] );

		// prune when all steps are larger
		// cannot prove the transitivity

		/* 	for( set<int>::const_iterator it = level_l_h[op->level].begin(); it!=level_l_h[op->level].end(); it++ )
		{
		a_res = a_res & ( resources_p[core][add][ currentSchedule_p[core][operations[*it]]  ]
		>= resource_snapshot_p[core][add][ optimalSchedule_p[core][operations[*it]]  ]);
		m_res = m_res & ( resources_p[core][multiplication][ currentSchedule_p[core][operations[*it]]  ]
		>= resource_snapshot_p[core][multiplication][ optimalSchedule_p[core][operations[*it]]  ]);
		}*/
		//	for ( int i=1; i<=step; i++ )
		//	{
		//		res_count += resources_p[core][add][i] - resource_snapshot_p[core][add][i];
		//		res_count += resources_p[core][multiplication][i] - resource_snapshot_p[core][multiplication][i];
		//	}

	}
	//  return temp_bool && (res_count>=0);
	//if(temp_bool && a_res && m_res) printf("level bound gets effect \n");
	// return temp_bool && a_res && m_res;
	if(temp_bool) printf("level bound gets effect \n");
	return temp_bool ;
}
// calculate Lh and Hh
void
	getLhHh( int *l, int *h, Operation * op )
{
	int level = op->level;
	set < int >opWithSameLevel;
	for( map < int, Operation * >::const_iterator it =
		operations.begin(); it != operations.end(); it++ )
	{
		Operation * op = ( *it ).second;
		if( op->level == level )
			opWithSameLevel.insert( op->id );
		else
			continue;
	}
	*l = *opWithSameLevel.begin();
	*h = *opWithSameLevel.rbegin();
}
int
	upperBound( Operation * op )
{
	int rs = 0;
	// similar to updateALAP except for using ALAP as the priority
	return rs;
}
// get low bound
int
	lowBound( Operation * op )
{
	map < type, map < int, int > >resources_ = resources;
	map < Operation *, int >tempSchedule = currentSchedule;
	// if( op->id == 28 )
	// int test = 0;
	FuncTimer::checkin( lowbound_t );
	int l = *level_l_h[op->level].begin();
	int h = *level_l_h[op->level].rbegin();
	int lowBoundTime = 0;
	int temp = 0;
	map < Operation *, int >start;
	// getLhHh( &l, &h, op );
	for( int k = l; k <= op->id; k++ )
	{
		Operation * op = operations[k];
		// if( lowBoundTime == 0 )
		// lowBoundTime = currentSchedule[op] + op->delay +
		// CPofSubGraph[op];
		// else
		lowBoundTime =
			max( lowBoundTime, currentSchedule[op] + CPofSubGraph[op]  );
	}
	for( int k = op->id + 1; k <= h; k++ )
	{
		Operation * opk = operations[k];
		set < Operation * >setOfImmediatePrecedent =
			immediatePrecedentOperations[opk];
		for( set < Operation * >::const_iterator it =
			setOfImmediatePrecedent.begin();
			it != setOfImmediatePrecedent.end(); it++ )
		{
			Operation * op = ( *it );
			temp = currentSchedule[op] + op->delay;
			start[opk] = max( temp, start[opk] );
		}
	}
	// int r = 0;
	/*
	*
	for( int k = op->id + 1; k <= h; k++ )
	{
	Operation * opk =
	* operations[k];
	r = max( optimalSchedule[opk], start[opk] + 1
	* );
	// r = start[opk] + 1;
	lowBoundTime = max( lowBoundTime, r
	* + CPofSubGraph[opk] );
	}
	*/
	for( int i = op->id + 1; i <= operations.size(); i++ )
	{
		int k = 0;
		for( int k = operations[i]->ASAP; k <= operations[i]->ALAP; k++ )
		{
			if( isPrecedence( operations[i], k ) )
			{
				// only occupy, no release is needed
				currentSchedule[operations[i]] = k;
				occupyResource( k, operations[i]->t, operations[i]->delay );
				break;
			}
		}
		//      k =
		//          max( currentSchedule[operations[i]], start[operations[i]] + 1 );
		lowBoundTime =
			max( lowBoundTime, k  + CPofSubGraph[operations[i]]  );
	}
	resources = resources_;
	currentSchedule = tempSchedule;
	FuncTimer::checkout( lowbound_t );
	// printf("low: %d\n", lowBoundTime);
	// if(lowBoundTime == optimalScheduleTime)
	// printf("*\n");
	return lowBoundTime;
}
int
	lowBound( int core, Operation * op )
{
	map < type, map < int, int > >resources_ = resources_p[core];
	map < Operation *, int >tempSchedule = currentSchedule_p[core];
	int endid = 0;
	if( op == NULL )
		endid = 0;
	else
		endid = op->id - 1;
	FuncTimer::checkin( lowbound_t );
	int lowBoundTime = 0;
	int temp = 0;
	map < Operation *, int >start;
	multiset < Operation > L_;
	map < int, int >L_array;
	map < int, int >S_;
	int w_ = 0;
	for( int i = 1; i <= endid; i++ )
	{
		Operation * op = operations[i]->sortedOp;
		lowBoundTime =
			max( lowBoundTime,
			currentSchedule_p[core][op] + CPofSubGraph[op]  );
	}
	/*
	if(op!=NULL)
	{
	int l = *level_l_h[op->level].begin();
	int h = *level_l_h[op->level].rbegin();
	for( int k = endid + 1; k <= h; k++ )
	{
	Operation * opk = operations[k];
	set < Operation * >setOfImmediatePrecedent =
	immediatePrecedentOperations[opk];
	for( set < Operation * >::const_iterator it =
	setOfImmediatePrecedent.begin();
	it != setOfImmediatePrecedent.end(); it++ )
	{
	Operation * op = ( *it );
	temp = currentSchedule_p[core][op] + op->delay;
	start[opk] = max( temp, start[opk] );
	}
	}
	}
	*/
	int maxid = 0;
	for( int i = endid + 1; i <= operations.size(); i++ )
	{
		int opid = operations[i]->sortedOp->id;
		int k=0;

		if(op==NULL)
			k = ASAPofMultiThread[core][operations[opid]];//, ASAPUC[operations[opid]]);
		else
			k = ASAPofMultiThread[core][operations[opid]];//, ASAPUC[operations[opid]]);

		//int k = operations[opid]->ASAP;
		//	int k = 1;
		while( true )
			//       for( int k = ASAPofMultiThread[core][operations[opid]];
				//               k <= operations[opid]->ALAP; k++ )
		{
			// only occupy, no release is needed
			if( isResourceAvailable( core, k,
				operations[opid]->t,
				operations[opid]->delay )
				//                    isPrecedence( core, operations[i], k )
				)
			{
				currentSchedule_p[core][operations[opid]] = k;
				occupyResource( core, k, operations[opid]->t,
					operations[opid]->delay );
				break;
			}
			k++;
		}
		//     k =
		//         max( currentSchedule_p[core][operations[opid]],
		//              start[operations[opid]] + 1 );
		//               printf("id: %d t:%d asap: %d cp:%d k:%d sum: %d\n", opid, operations[opid]->t, operations[opid]->ASAP,CPofSubGraph[operations[opid]], k, k + CPofSubGraph[operations[opid]]);
		lowBoundTime =
			max( lowBoundTime, k + CPofSubGraph[operations[opid]]  );
	}
	resources_p[core] = resources_;
	currentSchedule_p[core] = tempSchedule;
	return lowBoundTime;
}
// get all immediate precedent operations
set < Operation * >getImmediatePrecedent( Operation * op )
{
	set < Operation * >rs;
	for( set < Dependency * >::const_iterator it =
		dependencies.begin(); it != dependencies.end(); it++ )
	{
		if( ( *it )->sink == op )
		{
			Operation * op = ( *it )->source;
			rs.insert( op );
		}
	}
	return rs;
}
// determine whether resource of specified type is available
bool isResourceAvailable( int step, type t, int delay )
{
	FuncTimer::checkin( isResourceAvailable_t );
	//    if( resources[t].size() == 0 )
	//        resources[t].clear();
	for( int i = step; i < step + delay; i++ )
	{
		// occupy the for subsequent steps
		if( resources[t][i] >= resourcePool[t] )
		{
			FuncTimer::checkout( isResourceAvailable_t );
			return false;
		}
	}
	FuncTimer::checkout( isResourceAvailable_t );
	return true;
}
bool isResourceEqual( int core, int step, type t, int delay )
{
	FuncTimer::checkin( isResourceAvailable_t );
	//    if( resources_p[core][t].size() == 0 )
	//        resources_p[core][t].clear();
	for( int i = step; i < step + delay; i++ )
	{
		// occupy the for subsequent steps
		if( resources_p[core][t][i] + 1 != resourcePool[t] )
		{
			FuncTimer::checkout( isResourceAvailable_t );
			return false;
		}
	}
	FuncTimer::checkout( isResourceAvailable_t );
	return true;
}
bool isResourceAvailable( int core, int step, type t, int delay )
{
	FuncTimer::checkin( isResourceAvailable_t );
	//    if( resources_p[core][t].size() == 0 )
	//        resources_p[core][t].clear();
	for( int i = step; i < step + delay; i++ )
	{
		// occupy the for subsequent steps
		if( resources_p[core][t][i] >= resourcePool[t] )
		{
			FuncTimer::checkout( isResourceAvailable_t );
			return false;
		}
	}
	FuncTimer::checkout( isResourceAvailable_t );
	return true;
}
bool isPrecedence( Operation * op, int step, map < int, int >schedule )
{
	FuncTimer::checkin( isPrecedence_t );
	bool rs = true;
	set < Operation * >setOfImmediatePrecedent =
		immediatePrecedentOperations[op];
	for( set < Operation * >::const_iterator it =
		setOfImmediatePrecedent.begin();
		it != setOfImmediatePrecedent.end(); it++ )
	{
		Operation * op = ( *it );
		rs = rs & ( schedule[op->id] + op->delay <= step );
		if( rs == false )
		{
			FuncTimer::checkout( isPrecedence_t );
			return rs;
		}
	}
	/*
	*
	for( set<Dependency*>::const_iterator it =
	* dependencies.begin(); it != dependencies.end(); it++ )
	{
	if(
	* ( *it )->sink == op )
	{
	Operation * op = ( *it )->source;
	rs
	* = rs & ( currentSchedule[op] + op->delay <= step );
	if( rs
	* == false )
	return rs;
	}
	}
	*/
	FuncTimer::checkout( isPrecedence_t );
	return rs;
}
// determine whether the precedent operations has finished
bool isPrecedence( Operation * op, int step )
{
	FuncTimer::checkin( isPrecedence_t );
	bool rs = true;
	set < Operation * >setOfImmediatePrecedent =
		immediatePrecedentOperations[op];
	for( set < Operation * >::const_iterator it =
		setOfImmediatePrecedent.begin();
		//    printf("op%d have %d precedences\n", op->id, op->precedent.size());
		//    for( set < Operation * >::const_iterator it =
		//        op->precedent.begin();
		it != setOfImmediatePrecedent.end(); it++ )
	{
		Operation * op = ( *it );
		rs = rs & ( currentSchedule[op] + op->delay - 1 < step );
		if( !rs )
		{
			FuncTimer::checkout( isPrecedence_t );
			return rs;
		}
	}

	/*
	*
	for( set<Dependency*>::const_iterator it =
	* dependencies.begin(); it != dependencies.end(); it++ )
	{
	if(
	* ( *it )->sink == op )
	{
	Operation * op = ( *it )->source;
	rs
	* = rs & ( currentSchedule[op] + op->delay <= step );
	if( rs
	* == false )
	return rs;
	}
	}
	*/
	FuncTimer::checkout( isPrecedence_t );
	return rs;
}
bool isPrecedence( int core, Operation * op, int step )
{
	FuncTimer::checkin( isPrecedence_t );
	bool rs = true;
	set < Operation * >setOfImmediatePrecedent =
		immediatePrecedentOperations[op];
	for( set < Operation * >::const_iterator it =
		setOfImmediatePrecedent.begin();
		it != setOfImmediatePrecedent.end(); it++ )
	{
		Operation * op = ( *it );
		//     if( currentSchedule_p[core][op] == 0 )
		//        return false;
		rs = rs & ( currentSchedule_p[core][op] + op->delay - 1 < step );
		if( rs == false )
		{
			FuncTimer::checkout( isPrecedence_t );
			return rs;
		}
	}
	FuncTimer::checkout( isPrecedence_t );
	return rs;
}
set < Operation * >getSuccessor( Operation * op )
{
	set < Operation * >rs;
	Graph * subGraph = getSubGraph( op );
	for( set < Operation * >::const_iterator it =
		subGraph->operations.begin();
		it != subGraph->operations.end(); it++ )
	{
		rs.insert( ( *it ) );
	}
	rs.erase( op );
	return rs;
}
// initialize data structures of the given DFG
void
	initDFG()
{
	// get all sink operations and source operations of the DFG
	for( map < int, Operation * >::const_iterator it =
		operations.begin(); it != operations.end(); it++ )
	{
		Operation * op = ( *it ).second;
		sinkOperations.insert( op );
		sourceOperations.insert( op );
	}
	for( set < Dependency * >::const_iterator it =
		dependencies.begin(); it != dependencies.end(); it++ )
	{
		Dependency * dep = ( *it );
		sinkOperations.erase( dep->source );
		sourceOperations.erase( dep->sink );
	}
	// calculate level
	// printf( "Calculating level for ops...\n" );
	// for( set<Operation*>::const_iterator it =
	// sourceOperations.begin(); it != sourceOperations.end(); it++ )
	// {
	// Operation * op = ( *it );
	// DFS( op, 0 );
	// }
	// longest path algorithm
	floydWarshall();
	printf( "Initializing CP...\n" );
	CPofSubGraph.clear();
	CPofPredGraph.clear();
	CPofPreRevGraph.clear();
	CPofPredGraph_.clear();
	for( multiset<Operation>::const_iterator it = topoSet.begin(); it != topoSet.end(); it++ )
	{
		//       printf ("Processing op %d of %d\n", i, operations.size ());
		Operation * op = operations[it->id];
		CPofSubGraph[op] =
			getCriticalPathLength( op, getSubGraph( op ), cpofsub );
		CPofPredGraph[op] =
			getCriticalPathLength( op, getPrecedenceGraph( op ), cpofpred );
		CPofPredGraph_[op] = getCriticalPathLength( op, getPrecedenceGraph( op ), cpofpred_ );
		CPofPreRevGraph[op] =
			getCriticalPathLength( op, getPrecedenceGraph
			( op,
			getReversedGraph( getSubGraph( op ) ) ),
			cpofpredresv );
		//    level_l_h[CPofPredGraph_[op]].insert( op->id );
		//    level_count = max( level_count, CPofPredGraph_[op] );
	}
	printf( "Initializing Immediate Precedent...\n" );
	for( int i = 1; i <= operations.size(); i++ )
	{
		Operation * op = operations[i];
		immediatePrecedentOperations[op] = getImmediatePrecedent( op );
	}
	printf( "Initializing Successors...\n" );
	for( int i = 1; i <= operations.size(); i++ )
	{
		Operation * op = operations[i];
		successorOperations[op] = getSuccessor( op );
	}
	printf( "Initializing ASAP...\n" );
	initASAP();
}
void
	getBadSchedule()
{
	int step = 1;
	for( int i = 1; i <= operations.size(); i++ )
	{
		currentSchedule[operations[i]] = optimalSchedule[operations[i]] =
			badSchedule[operations[i]] = step;
		step += operations[i]->delay;
	}
	optimalScheduleTime = badScheduleTime = w = step;
	fout << "bad schedule: " << step << "\n";
}
void
	preEnumaration()
{
	resources.clear();
	//	basicEnu( 1 );
	//	resources.clear();
	printf( "Listing...\n" );
	currentSchedule.clear();
	listingSchedule.clear();
	resources.clear();

	srand ((unsigned)time(0));

	//for(int i=0;i<100;i++)
	{
		listSchedule(byasap);
		int list1 = listSchedulingTime;
		optimalScheduleTime = w = list1;
		optimalSchedule = listingSchedule;
		listSchedule(byalap);
		int list2 = listSchedulingTime;

		if(list1>list2)
		{
			global_listorder = byalap;
			optimalScheduleTime = w = listSchedulingTime = list2;
			optimalSchedule = listingSchedule;
		}
		else
		{
			global_listorder = byasap;
			optimalScheduleTime = w = listSchedulingTime = list1;
			optimalSchedule = listingSchedule = optimalSchedule;
		}
	}

	// global_listorder = byasap;

	// getBadSchedule();
	printf( "Initializing ALAP...\n" );
	initALAP();
	sortedSetByALAP.clear();
	for( int i = 1; i <= operations.size(); i++ )
	{
		//		operations[i]->sort_id = -operations[i]->ASAP ;
		operations[i]->sort_id = -operations[i]->ASAP;
		sortedSetByALAP.insert( *operations[i] );
	}
	writeSchedule( "ALAP" );

	new_low = compute_lower_bound();
	fout << "\nglobal low: " << globalLow << " new low: " << new_low << "\n";
	printf("new low: %d\n", new_low);
}
// initialize best schedule and best schedule time
void
	initOptimalSchedule()
{
	for( map < int, Operation * >::const_iterator it =
		operations.begin(); it != operations.end(); it++ )
	{
		Operation * op = ( *it ).second;
		optimalSchedule[op] = op->id;
	}
	optimalScheduleTime = w = 20;
}
// give a feasible list schedule and w
void
	listSchedule()
{
	map < type, map < int, int > >resources_ = resources;
	multiset < Operation > L_;
	map < int, int >L_array;
	int w_ = 0;
	for( int i = 1; i <= operations.size(); i++ )
	{
		// printf( "listSchedule: processing op %d...\n", i );
		operations[i]->sort_id = -operations[i]->ASAP;// CPofSubGraph[operations[i]];
		//operations[i]->sort_id = -operations[i]->id;
		L_.insert( *operations[i] );
	}
	int count = 1;
	for( multiset < Operation >::iterator it = L_.begin();
		it != L_.end(); it++ )
	{
		L_array[count] = ( *it ).id;
		count++;
	}
	//    for( int l = operations[L_array[1]]->ASAP; l <= operations[L_array[1]]->ASAP + 10; l++ )
	//    {
	//        resources = resources_;

	for( int k = 1; k <= operations.size(); k++ )
	{

		Operation * opk = operations[L_array[k]];
		printf("list sequence: op%d with cp%d\n",L_array[k], CPofSubGraph[opk] );
		int j =  opk->ASAP;
		while( true )
		{
			//     printf( "listSchedule: stepping op %d...\n", j );
			if( isPrecedence( opk, j )
				&& isResourceAvailable( j, opk->t, opk->delay ) )
			{
				// only occupy, no release is needed
				occupyResource( j, opk->t, opk->delay );
				listingSchedule[opk] = currentSchedule[opk] = j;
				break;
			}
			j++;
		}
	}
	for( int m = 1; m <= operations.size(); m++ )
	{
		Operation * op = operations[L_array[m]];
		w_ = max( listingSchedule[op] + op->delay - 1, w_ );
	}
	listSchedulingTime = w_;
	optimalScheduleTime = w = min( w, w_ );
	//printf("list length: %d\n", listSchedulingTime);
	//        l++;
	//    }
	// restore resource usage pool
	resources = resources_;
}

void
	listSchedule(listorder lo)
{    float magic = 0;
map < type, map < int, int > >resources_ = resources;
multiset < Operation > L_;
map < int, int >L_array;
int w_ = 0;
for( int i = 1; i <= operations.size(); i++ )
{
	magic = 0;//rand()/((double)RAND_MAX+0.5);
	//   printf("magic: %f\n", magic);
	// printf( "listSchedule: processing op %d...\n", i );
	switch (lo) {
	case byasap:
		operations[i]->sort_id = -operations[i]->ASAP - magic;
		break;
	case byalap:
		operations[i]->sort_id = CPofSubGraph[operations[i]] - magic;
		break;

	default:
		break;
	}
	L_.insert( *operations[i] );
}
int count = 1;
for( multiset < Operation >::iterator it = L_.begin();
	it != L_.end(); it++ )
{
	L_array[count] = ( *it ).id;
	count++;
}
//    for( int l = operations[L_array[1]]->ASAP; l <= operations[L_array[1]]->ASAP + 10; l++ )
//    {
//        resources = resources_;

for( int k = 1; k <= operations.size(); k++ )
{

	Operation * opk = operations[L_array[k]];
	//   printf("list sequence: op%d with cp%d\n",L_array[k], CPofSubGraph[opk] );
	int j =  opk->ASAP;
	while( true )
	{
		//     printf( "listSchedule: stepping op %d...\n", j );
		if( isPrecedence( opk, j )
			&& isResourceAvailable( j, opk->t, opk->delay ) )
		{
			// only occupy, no release is needed
			occupyResource( j, opk->t, opk->delay );
			listingSchedule[opk] = currentSchedule[opk] = j;
			break;
		}
		j++;
	}
}
for( int m = 1; m <= operations.size(); m++ )
{
	Operation * op = operations[L_array[m]];
	w_ = max( listingSchedule[op] + op->delay - 1, w_ );
}
listSchedulingTime = w_;
//optimalScheduleTime = w = min( w, w_ );
// printf("list length: %d\n", listSchedulingTime);
//        l++;
//    }
// restore resource usage pool
resources = resources_;
}

void resetContext()
{
	resources.clear();
	completeBranchBound = false;
	total_traverse = 0;
	maxOpTraversed = 0;
	optimalScheduleTime = w = listSchedulingTime;
	currentSchedule = optimalSchedule = listingSchedule;
	FuncTimer::init();
	currentSchedule_p[1] = optimalSchedule;
	optimalSchedule_p[1] = optimalSchedule;
	resources_p.clear();
	resource_snapshot_p.clear();
	for( map < int, Operation * >::const_iterator it =
		operations.begin(); it != operations.end(); it++ )
		ASAPofMultiThread[1][( *it ).second] = ( *it ).second->ASAP;
	for( map < int, Operation * >::const_iterator it =
		operations.begin(); it != operations.end(); it++ )
		ALAPofMultiThread[1][( *it ).second] = ( *it ).second->ALAP;
}
void
	printResult( fstream * fout )
{
	*fout << "The optimal schedule time is " << optimalScheduleTime <<
		"\n";
	for( map < Operation *, int >::const_iterator it =
		optimalSchedule.begin(); it != optimalSchedule.end(); it++ )
	{
		Operation * op = ( *it ).first;
		int step = ( *it ).second;
		*fout << op->id << "\t" << optimalSchedule[op] << "\n";
	}
	*fout << "Finished branchbound? " << completeBranchBound << "\n";
}
void parallelTestDriver( void * arg )
{
	resetContext();
	parallel_ag * pa = ( parallel_ag* )arg;
	core_number = pa->core_limit;
	char info[256];
	sprintf_s( info, "using %d core(s) to perform...\n", core_number );
	printInfo( info );
	//pa->assignmentSemaphore = CreateSemaphore( NULL, 1, 1, NULL );
	//	sem_init( &pa->assignmentSemaphore, 1, 1 );
	for( int i = 1; i <= assignment; i++ )
		pa->assignmentMap.insert( i );
	for( int i = 1; i <= core_number; i++ )
	{
		currentSchedule_p[i] = basicSchedule;
		optimalSchedule_p[i] = basicSchedule;
		resources_p[i].clear();
		resource_snapshot_p[i].clear();
		for( map < int, Operation * >::const_iterator it =
			operations.begin(); it != operations.end(); it++ )
		{
			//   printf("ASAPofMultiThread[%d] = %d\n", i,  ( *it ).second->ASAP);
			ASAPofMultiThread[i][( *it ).second] = ( *it ).second->ASAP;
		}
	}
	long branch_with_parallel_start = dGetTickCount();
	long branch_with_parallel_end = 0;
	long branch_with_parallel_duration = 0;
	int count = 0;
	while( branch_with_parallel_duration < 10 )
	{


		for( int i = 1; i <= core_number; i++ )
		{
			thread_ag * ta = ( thread_ag * ) malloc( sizeof( thread_ag ) );
			if( core_number >= assignment )
			{
				ta->lower = i;
				ta->upper = i;
			}
			else
			{
				ta->lower =
					( i - 1 ) * assignment / ( unsigned int )( core_number ) * 1.0 +
					1;
				ta->upper =
					( i +
					1 ) * ( assignment / ( unsigned int )( core_number ) ) * 1.0 >
					assignment ? assignment : ( i ) * assignment /
					( unsigned int )( core_number ) * 1.0;
			}
			ta->coreID = i;
			ta->assignmentMap = &pa->assignmentMap;
			//	ta->assignmentSemaphore = &pa->assignmentSemaphore;
			// threadMap[i] = ( int )_beginthread( coreScheduler, 0, ( void* )ta );//
			printf("started thread on core %d\n", ta->coreID);
			//	pthread_create(&threadMap[i], NULL, (void*(*)(void*))coreScheduler, (void*)(ta));
			// SetThreadPriority( threadMap[i],
			// THREAD_PRIORITY_HIGHEST );
			// SetThreadAffinityMask( threadMap[i], ( DWORD_PTR
			// )coreNumber );
			// WaitForSingleObject( threadMap[i], INFINITE );



		}
		for( int i = 1; i <= core_number; i++ )
			//WaitForSingleObject( threadMap[i], INFINITE );
				//		pthread_join( threadMap[i], NULL );

					branch_with_parallel_end = dGetTickCount();
		branch_with_parallel_duration =
			branch_with_parallel_end - branch_with_parallel_start;
		count++;
	}
	// add_count--;
	// multi_count--;
	// if( add_count == 0 || multi_count == 0 )
	// break;
	// resourcePool[( enum type ) 1] = add_count;
	// resourcePool[( enum type ) 2] = multi_count;
	// listSchedule();
	// initALAP();
	// }
	fout.flush();
	fout << "parallel total duration: " << ( branch_with_parallel_duration )
		* 1.0 / count << "with core " << core_number << "\n";
}

void validateSchedule(map<Operation*, int> Schedule, map < type, map < int, int > > resources)
{

}

int compute_lower_bound()
{
	int cp = 0;
	for( set<Operation*>::iterator it = sinkOperations.begin(); it != sinkOperations.end(); it++ )
	{
		Operation * op = *it;
		op->asapuc = ASAPUC[op] = compute_asapuc(op);
		cp = max(op->asapuc, cp);
	}
	//  printf("top cp: %d\n", cp);
	compute_alapuc(sinkOperations, cp);
	return(greedy_lower_bound(sinkOperations, cp));

}

// done
int compute_asapuc(Operation* op)
{
	if(sourceOperations.find(op) != sourceOperations.end())
	{
		op->alapuc = 1; // todo: corrent? or op->ALAP;
		return op->ASAP;
	}
	else {
		return recursive_lower_bound(op);
	}
}

// done
void compute_alapuc(set<Operation*> R, int CP)
{
	Operation * root;
	set < Operation * > target_nodes;
	int temp_cp;

	for( set < Operation * >::const_iterator it =
		R.begin(); it != R.end(); it++ )
	{
		Operation * op = ( *it );
		temp_cp = CPofPredGraph[op];
		root = op;
		Graph * subgraph = getPrecedenceGraph(op);
		//    printf("subgraph of op%d contains %d children\n", op->id, subgraph->operations.size());
		for( set<Operation*>::iterator it = subgraph->operations.begin(); it!=subgraph->operations.end(); it++)
		{
			Operation * child = *it;
			target_nodes.insert(child);
		}
	}

	//   printf("greedy: target number: %d\n", target_nodes.size());

	map < type, map < int, int > >resources_ = resources_p[1];
	map < Operation *, int >tempSchedule = currentSchedule_p[1];

	resources_p[1].clear();
	currentSchedule_p[1].clear();

	int upperBoundTime = 0;
	int temp = 0;
	map < Operation *, int >start;
	multiset < Operation > L_;
	map < int, int >L_array;
	map < int, int >S_;
	int w_ = 0;

	//   printf("greedy: constrauct L_\n");
	for( set < Operation * >::const_iterator it =
		target_nodes.begin(); it != target_nodes.end(); it++ )
	{
		Operation * op = ( *it );
		// printf( "listSchedule: processing op %d...\n", i );
		op->sort_id = -op->ALAP;
		//operations[i]->sort_id = -operations[i]->id;
		L_.insert( *op );
	}

	//  printf("greedy: constrauct L_array\n");
	int count = 1;
	for( multiset < Operation >::iterator it = L_.begin();
		it != L_.end(); it++ )
	{
		L_array[count] = ( *it ).id;
		count++;
	}

	int maxid = 0;
	for( int i = 1; i<=target_nodes.size(); i++ )
	{
		Operation * op = operations[L_array[i]];
		//       printf("op%d asap:%d asapuc:%d | alap:%d alapuc:%d\n", op->id, op->ASAP, op->asapuc, op->ALAP, op->alapuc);

		int k = op->asapuc;

		while(true)
		{
			// only occupy, no release is needed
			if( isResourceAvailable( 1, k,
				op->t,
				op->delay )
				&& isPrecedence( 1, op, k )
				)
			{
				currentSchedule_p[1][op] = k;
				occupyResource( 1, k, op->t,
					op->delay );
				break;
			}
			k++;
		}

		upperBoundTime =
			max( upperBoundTime, k + op->delay - 1);
	}

	//  printf("compute_alapuc: upperBoundTime %d, cp %d\n", upperBoundTime, CP);
	if(R.size()==1)
	{
		//   printf("max gap: %d\n", lowBoundTime);
		for( set < Operation * >::const_iterator it =
			target_nodes.begin(); it != target_nodes.end(); it++ )
		{
			Operation * op = ( *it );
			// printf( "listSchedule: processing op %d...\n", i );
			//       printf("cpofnoes: from %d to %d:%d\n", op->id, root->id, CPofNodes[op][root]);
			op->alapuc = ALAPUC[op] = upperBoundTime - CPofNodes[op][root] - root->delay + 1;
		}
	}
	else
	{
		for( set < Operation * >::const_iterator it =
			target_nodes.begin(); it != target_nodes.end(); it++ )
		{
			Operation * op = ( *it );
			// printf( "listSchedule: processing op %d...\n", i );
			//        printf("cpofsubgraph: from %d cp %d\n", op->id, CPofSubGraph[op]);
			op->alapuc = ALAPUC[op] = upperBoundTime - CPofSubGraph[op];
		}
	}


	resources_p[1] = resources_;
	currentSchedule_p[1] = tempSchedule;
}

int greedy_lower_bound(set<Operation*> R, int CP)
{
	//  printf("greedy cp: %d\n", CP);
	set < Operation * > target_nodes;
	Operation * root;

	for( set < Operation * >::const_iterator it =
		R.begin(); it != R.end(); it++ )
	{
		Operation * op = ( *it );
		root = op;
		Graph * subgraph = getPrecedenceGraph(op);
		//      printf("subgraph of op%d contains %d children\n", op->id, subgraph->operations.size());
		for( set<Operation*>::iterator it = subgraph->operations.begin(); it!=subgraph->operations.end(); it++)
		{
			Operation * child = *it;
			target_nodes.insert(child);
		}
	}

	//   printf("greedy: target number: %d\n", target_nodes.size());

	map < type, map < int, int > >resources_ = resources_p[1];
	map < Operation *, int >tempSchedule = currentSchedule_p[1];

	resources_p[1].clear();
	currentSchedule_p[1].clear();

	int lowBoundTime = 0;
	int temp = 0;
	map < Operation *, int >start;
	multiset < Operation > L_;
	map < int, int >L_array;
	map < int, int >S_;
	int w_ = 0;

	//   printf("greedy: constrauct L_\n");
	for( set < Operation * >::const_iterator it =
		target_nodes.begin(); it != target_nodes.end(); it++ )
	{
		Operation * op = ( *it );
		// printf( "listSchedule: processing op %d...\n", i );
		op->sort_id = -op->ALAP;
		//operations[i]->sort_id = -operations[i]->id;
		L_.insert( *op );
	}

	//   printf("greedy: constrauct L_array\n");
	int count = 1;
	for( multiset < Operation >::iterator it = L_.begin();
		it != L_.end(); it++ )
	{
		L_array[count] = ( *it ).id;
		count++;
	}

	int maxid = 0;
	for( int i = 1; i<=target_nodes.size(); i++ )
	{
		Operation * op = operations[L_array[i]];


		int k = op->asapuc;

		while(true)
		{
			// only occupy, no release is needed
			if( isResourceAvailable( 1, k,
				op->t,
				op->delay )
				//                    isPrecedence( core, operations[i], k )
				)
			{
				currentSchedule_p[1][op] = k;
				occupyResource( 1, k, op->t,
					op->delay );
				break;
			}
			k++;
		}


		if(R.size()==1)
		{
			//        printf("op%d asap:%d asapuc:%d | alap:%d alapuc:%d kstep: %d low:%d\n", op->id, op->ASAP, op->asapuc, op->ALAP, op->alapuc, k, k + CPofNodes[op][root] + root->delay - 1);
			lowBoundTime =
				max( lowBoundTime, k + CPofNodes[op][root] );
		}
		else
		{
			//          printf("op%d asap:%d asapuc:%d | alap:%d alapuc:%d kstep: %d low:%d\n", op->id, op->ASAP, op->asapuc, op->ALAP, op->alapuc, k, k + CPofSubGraph[op]);
			lowBoundTime =
				max( lowBoundTime, k + CPofSubGraph[op]);
		}
	}


	//  printf("max gap: %d\n", lowBoundTime);


	resources_p[1] = resources_;
	currentSchedule_p[1] = tempSchedule;
	return lowBoundTime;
}

// done
int compute_critical_path(Operation* op)
{
	int rs = 0;
	for(set<Operation*>::iterator it = op->precedent.begin(); it != op->precedent.end(); it++)
	{
		Operation * pre = *it;
		rs = max(rs, pre->asapuc + pre->delay - 1 );
	}
	return rs;
}

// done
int recursive_lower_bound(Operation* op)
{
	for(set<Operation*>::iterator it = op->precedent.begin(); it != op->precedent.end(); it++)
	{
		Operation * pre = *it;
		//      printf("recur: op%d 's asapuc %d\n", pre->id, pre->asapuc);
		if( pre->asapuc == 0 )
			pre->asapuc = ASAPUC[pre] = compute_asapuc(pre);
	}

	int CP = op->asapuc = compute_critical_path(op);
	set<Operation*> nodes;
	nodes.insert(op);
	compute_alapuc(nodes, op->asapuc);
	return(greedy_lower_bound(nodes, CP));
}

int main( int argc, char **argv )
{
	bool config_multithread;
	int config_add;
	int config_multi;
	bool config_multiround;
	const char ConfigFile[] = "config.txt";
	Config configSettings( ConfigFile );
	config_multithread = configSettings.Read( "multithread", false );
	config_add = configSettings.Read( "add", 0 );
	config_multi = configSettings.Read( "multi", 0 );
	config_multiround = configSettings.Read( "multiround", false );
	config_echo = configSettings.Read( "echo", false );
	config_low = configSettings.Read( "low", false );
	config_level = configSettings.Read( "level", false );
	FuncTimer::init();
	ifstream fin2( "target.txt" );
	string filename;
	fstream latexout;
	latexout.open( "latex.txt", ios::out );
	while( getline( fin2, filename ) )
	{
		ifstream fin3( "resource.txt", ios::in );
		while( !fin3.eof() )
		{
			int add_number = 0, multi_number = 0;
			fin3 >> add_number >> multi_number;
			char str[256];
			sprintf_s( str, "process file %s with %d adders and %d multipliers\n", filename.c_str(), add_number, multi_number );
			printInfo( str );
			char rsFileName[256];
			sprintf_s( rsFileName, "%s_rs_%d%d.txt", filename.c_str(), add_number, multi_number );
			fout.open( rsFileName, ios::out );
			// fstream fin( argv[1], ios::in );
			// fstream fin( "AR_r.txt", ios::in );
			fstream fin( filename.c_str(), ios::in );
			// fout.open( argv[2], ios::out );
			int operation_count,
				constraint_count, add_count, multi_count, add_delay, multi_delay,
				level, graph;
			fin >> operation_count >> constraint_count >> add_count >> multi_count
				>> add_delay >> multi_delay;
			fout << "total operations: " << operation_count << "\n";
			fout << "total constraints: " << constraint_count << "\n";
			add_count = add_number;
			multi_count = multi_number;
			fout << "total adder: " << add_count << "\n";
			fout << "total muliplier: " << multi_count << "\n";
			resourcePool[( enum type ) 1] = add_count;
			resourcePool[( enum type ) 2] = multi_count;
			printf( "Reading from test case file...\n" );
			for( int i = 0; i < operation_count; i++ ) // serious bug i starts from 1 not 0
			{
				int id, type;
				fin >> id >> type >> level >> graph;
				fout << id << " " << type << "\n";
				Operation * op = new Operation();
				op->base_addr = op;
				op->id = id;                // kritische Frage hier: id oder i?
				op->visited = false;
				op->CPofPreRevGraph = -1;
				op->CPPredGraph = -1;
				op->CPSubGraph = -1;
				op->level = level;
				op->graph = graph;
				graph_count = max( graph_count, graph );
				if( type == add )
				{
					op->t = add;
					op->delay = add_delay;
				}
				else if( type == multiplication )
				{
					op->t = multiplication;
					op->delay = multi_delay;
				}
				operations[id] = op;
			}
			for( int i = 0; i < constraint_count; i++ )
			{
				int id, source, sink;
				fin >> source >> sink;
				fout << i << " " << source << " " << sink << "\n";
				Dependency * dep = new Dependency();
				dep->id = i;
				dep->sink = operations[sink];
				dep->source = operations[source];
				dependencies.insert( dep );
				operations[source]->adj.insert( dep );
				operations[sink]->in.insert( dep );
				operations[source]->children.insert(operations[sink]);
				operations[sink]->precedent.insert(operations[source]);
			}
			// invoke the algorithm
			topoSort();
			initDFG();
			// while( add_count != 0 && multi_count != 0 )
			// {
			preEnumaration();
			if( true )
			{
				int count = 1;
				for( multiset < Operation >::iterator it = sortedSetByALAP.begin();
					it != sortedSetByALAP.end(); it++ )
				{
					operations[count]->sortedOp = operations[( *it ).id];
					count++;
					endofLevel[( *it ).level] = ( *it ).id;
				}
			}
			fout << "++++++++++++++++++++++++++\n";
			fout << "current adder: " << add_count << "\n";
			fout << "current muliplier: " << multi_count << "\n";
			printf( "Estimated space: %d\n", getEstimatedSpace() );
			fout << "Estimated space: " << getEstimatedSpace() << " \n";
			fout << "\nList scheduling\n";
			fout << "The list schedule time is " << listSchedulingTime << "\n";
			for( int i = 1; i <= operations.size(); i++ )
			{
				Operation * op = operations[i];
				fout << op->id << "\t" << listingSchedule[op] << " " << op->
					ASAP << " " << op->ALAP << " " << op->asapuc
					<< " " << op->alapuc << " " << CPofSubGraph[op] << "\n";
			}
			fout.flush();
			resetContext();

			latex_global = globalLow = lowBound( 1, NULL );
			printf("global low: %d\n", globalLow);
			latex_global = globalLow = max(new_low ,globalLow);

			testDriver( "composite", true, true, true, false );
			//     testDriver( "bulb", false, false, false, false );

			fout.flush();
			// test multi thread
			if( config_multithread )
			{
				printf( "start parallel algorithm...\n" );
				assignment = operations[1]->ALAP;
				//	map<int, pthread_t> parallelSet;//
				for( int core_count = 4; core_count <= 4; core_count = core_count * 2 )
				{
					parallel_ag pa;
					pa.core_limit = core_count;
					pa.assignmentMap.clear();
					printf( "starting parallelSet %d\n", core_count );
					//             parallelSet[core_count] = ( int* )_beginthread( parallelTestDriver, NULL, ( void* )&pa );
					//WaitForSingleObject( parallelSet[core_count], INFINITE );
					//		pthread_create(&parallelSet[core_count], NULL, (void*(*)(void*))parallelTestDriver, (void*)&pa);
					//		pthread_join( parallelSet[core_count], NULL );

					//                    parallelSet[core_count] = t;

				}
			}
			// test multi thread ==
			printf( "Finished...\n" );
			fout << "-------------------------------------------\n";
			fout.flush();
			fout.close();
		}
	}
	for(int l=0; l<history_level_info.size(); l++)
	{
		if(history_level_info[l]!=NULL)
			delete history_level_info[l];// = new vector<int>();
	}

	// check the correctness of the found optimal scheduling
	resources_p.clear();
	currentSchedule_p[1].clear();
	for( int i=1; i<=operations.size(); i++)
	{

		Operation * op = operations[i]->sortedOp;
		int step = optimalSchedule_p[1][op];
		printf("checking op%d at step %d\n", op->id, step);
		if(!isResourceAvailable(1, step, op->t, op->delay))
			printf("wrong scheduling due to resource conflict at step %d of op %d\n", step, op->id);
		if(!isPrecedence(1, op, step))
			printf("wrong scheduling due to precedent conflict at step %d of op %d\n", step, op->id);
		currentSchedule_p[1][op] = step;
		occupyResource(1, step, op->t, op->delay);
	}

	latexout.flush();
	latexout.close();
	fin2.close();
	return 0;
}
